/**
 * Copyright © 2021 易久批信息技术有限公司. All rights reserved.
 */
package com.dysm.binarytree;

/**
 *
 * @author xiay
 * @since 2021/1/18 10:45 下午
 */
public class BinaryTreeImpl implements BinaryTree {

    private MyNode root;

    public BinaryTreeImpl() {
    }

    public BinaryTreeImpl(MyNode root) {
        this.root = root;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public int getSize() {
        return getSizeRecursive(root);
    }

    private int getSizeRecursive(MyNode node) {
        if (node == null) {
            return 0;
        }
        return getSizeRecursive(node.getLeftNode()) + getSizeRecursive(node.getRightNode()) + 1;

    }

    public int getHeight() {
        return getHeightRecursive(root);
    }

    private int getHeightRecursive(MyNode node) {
        if (node == null) {
            return 0;
        }
        int hl = getHeightRecursive(node.getLeftNode());
        int hr = getHeightRecursive(node.getRightNode());
        return hl > hr ? hl + 1 : hr + 1;
    }

    public MyNode findKey(int key) {
        return findKeyRecursive(root, key);
    }
    
    private MyNode findKeyRecursive(MyNode node, int key) {
        if (node == null) {
            return null;
        }
        if (node.getValue() == key) {
            return node;
        }
        MyNode leftNode = findKeyRecursive(node.getLeftNode(), key);
        if (leftNode != null) {
            return leftNode;
        }
        MyNode rightNode = findKeyRecursive(node.getRightNode(), key);
        if (rightNode != null) {
            return rightNode;
        }
        return null;
    }

    public void beforeTraverse() {
        beforeTraverseRecursive(root);

    }

    private void beforeTraverseRecursive(MyNode node) {
        if (node == null) {
            return;
        }
        // 根
        System.out.print(node.getValue() + "   ");
        // 左子树
        beforeTraverseRecursive(node.getLeftNode());
        // 右子树
        beforeTraverseRecursive(node.getRightNode());
    }

    public void centerTraverse() {
        centerTraverseRecursive(root);
    }

    private void centerTraverseRecursive(MyNode node) {
        if (node == null) {
            return;
        }
        // 左子树
        centerTraverseRecursive(node.getLeftNode());
        // 根
        System.out.print(node.getValue() + "   ");
        // 右子树
        centerTraverseRecursive(node.getRightNode());
    }

    public void afterTraverse() {
        afterTraverseRecursive(root);
    }

    private void afterTraverseRecursive(MyNode node) {
        if (node == null) {
            return;
        }
        // 左子树
        afterTraverseRecursive(node.getLeftNode());
        // 右子树
        afterTraverseRecursive(node.getRightNode());
        // 根
        System.out.print(node.getValue() + "   ");
    }
}
